package main

import "fmt"

/*
	给定一个数组，将数组中的元素向右移动k个位置，其中k是非负数
	进阶：
		1.尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题
		2.你可以使用空间复杂度为O(1)的原地算法解决这个问题吗
*/
func rotate(nums []int, k int){
	//1.使用辅助数组
	//newArray := make([]int,len(nums))
	//for i:=0;i<len(nums);i++{
	//	newArray[(i+k)%len(nums)] = nums[i]
	//}
	//for j:=0;j<len(nums);j++{
	//	nums[j] = newArray[j]
	//}

	//2.将数组看作环形，使用temp储存被换数据，count记录已经调换过得数据
	//从零开始
	//注意零碎的点，各变量应该怎么变化
	//n := len(nums)
	//temp := nums[0]
	//count := 0
	//x := 0
	//for i:=0;;{
	//	x = i
	//	temp = nums[i]
	//	if count==n{
	//		break
	//	}
	//	for{
	//		if count==n{
	//			break
	//		}
	//		//交换当前与nums[(x+k)%n]
	//		temp, nums[(x+k)%n] = nums[(x+k)%n], temp
	//		x = (x+k)%n
	//		count++
	//		if(x==i){
	//			break
	//		}
	//	}
	//	//指针向前一步
	//	i++
	//}

	//3.数组反转
	//(1)先全部反转
	n := len(nums)
	k = k%n
	if k>0{
		for i:=0;i<n>>1;i++{
			nums[i],nums[n-i-1]=nums[n-i-1],nums[i]
		}
		//2.反转[0,k mod n-1]
		for j:=0;j<k>>1;j++{
			nums[j],nums[k-j-1] = nums[k-j-1],nums[j]
		}
		//3.反转[k mod n,n-1]
		for x:=0;x<(n-k)>>1;x++{
			nums[k+x],nums[n-1-x] = nums[n-1-x],nums[k+x]
		}
	}

	//答案的写法更elegant
	n = len(nums)
	k = k%n
	reverse(nums,0,n-1)
	reverse(nums,0,k-1)
	reverse(nums,k,n-1)
}

func reverse(nums []int, start, end int){
	for{
		if start>=end{
			break
		}
		nums[start],nums[end] = nums[end],nums[start]
		start++
		end --
	}
}
func main(){
	nums := []int{1,2,3,4,5,6,7}
	rotate(nums,3)
	fmt.Println("")
	//rotate(nums,0)
}
